// https://www.lintcode.com/problem/maximum-subarray-difference/

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: An integer indicate the value of maximum difference between two substrings
     */
    public int maxDiffSubArrays(int[] nums) {
        // write your code here
        // 记录从0到i的最大值和从n - 1到i的最小值，计算最大差。
        // 因为比较大的部分可能出现在前半段，也有可能出现在后半段，
        // 所以反转数组再计算一遍。
        int ret = _maxDiffSubArrays(nums);
        reverse(nums);
        return Math.max(ret, _maxDiffSubArrays(nums));
    }
    
    private int _maxDiffSubArrays(int[] nums) {
        int nlen = nums.length;
        int[] max_from_left = new int[nlen];
        int[] min_from_right = new int[nlen];
        Arrays.fill(max_from_left, 0);
        Arrays.fill(min_from_right, 0);
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int sum = 0;
        for (int i = 0; i < nlen; ++i) {
            sum += nums[i];
            max = Math.max(sum, max);
            if (sum < 0) {
                sum = 0;
            }
            max_from_left[i] = max;
        }
        sum = 0;
        for (int i = nlen - 1; i >= 0; --i) {
            sum += nums[i];
            min = Math.min(sum, min);
            if (sum > 0) {
                sum = 0;
            }
            min_from_right[i] = min;
        }
        int ret = Integer.MIN_VALUE;
        for (int i = 1; i < nlen; ++i) {
            ret = Math.max(ret, Math.abs(max_from_left[i - 1] - min_from_right[i]));
        }
        return ret;
    }
    
    private void reverse(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
            ++i;
            --j;
        }
    }
}